package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/9/20 9:50 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 */
public class _121_买卖股票的最佳时机_03 {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }


        int maxProfit = 0;
        int[] divs = new int[prices.length];
        divs[prices.length - 1] = prices.length - 1;
        for (int i = prices.length - 2; i >= 0 ; i--) {

            if (prices[i] <= prices[i + 1]) {

                divs[i] = divs[i+1];
            }else {

                if (prices[i] >= prices[divs[i+1]]) {

                    divs[i] = i;
                }else {

                    divs[i] = divs[i+1];
                }
            }

            maxProfit = Math.max(maxProfit,prices[divs[i]] - prices[i]);
        }

//        System.out.println(Arrays.toString(divs));

        return maxProfit;
    }
}
